#ifndef HEAD_H
#define HEAD_H
#include<iostream>
using namespace std;

struct node{
    node* nx;
    int data;
};

class arraylist{
private:
    node*ha;
    node*hb;
    int a_length;
    int b_length;

public:
    arraylist();
    ~arraylist();
    void destroylist(node*);
    node *creatlist(node*head, int length);
    int length_input();
    void showlist(node*);
    void mergeAB();
};


arraylist::arraylist(){
    cout<<endl<<"please input the length of arraylist A:";
    a_length=length_input();
    cout<<endl<<"please input the length of arraylist B:";
    b_length=length_input();
    ha=new node;
    hb=new node;
    cout<<"A ";
    ha=creatlist(ha,a_length);
    cout<<"B ";
    hb=creatlist(hb,b_length);
    showlist(ha);
    showlist(hb);
}




int arraylist::length_input(){
    int length;
    cin>>length;
        if(length){
            return length;
        }
        else{
            length_input();
        }
        return length;
}



node* arraylist::creatlist(node *head,int length){
    int i=0;
    node*p=head;
    cout<<"input elements:";
    while(i<length){
        p=p->nx=new node;
        cin>>p->data;
        i++;
    }
    p->nx=NULL;
    return head;
}

void arraylist::showlist(node *head){
    node*p=head;
    cout<<endl;
    while(p->nx!=NULL){
        p=p->nx;
        cout<<p->data<<"\t";
    }
}

arraylist::~arraylist(){
    destroylist(ha);
    destroylist(hb);
}


void arraylist::destroylist(node *head){
    node*p=head;
    while(head){
        p=head;
        head=head->nx;
        delete p;
    }
    head=NULL;
}

void arraylist::mergeAB(){
    node* newhead;
    node*na,*nb,*nc;
    na=ha->nx;
    nb=hb->nx;
    newhead=nc=ha;

    while(na&&nb){
        if(na->data<=nb->data){
            nc->nx=na;
            nc=na;
            na=na->nx;
        }
        else{
            nc->nx=nb;
            nc=nb;
            nb=nb->nx;
        }
    }
    //若有a,b有剩余，插入剩余部分
    if(nc->nx=na){
        nc->nx=na;
    }
    else{
        nc->nx=nb;
    }
    delete hb;
    showlist(ha);
}

#endif // HEAD_H
